package mtest3.day5;

public class Demo2 {
    public static void main(String[] args) {
        int[] arr = new int[]{11, 19, 5, 4, 7, 13, 2, 10, 30};

        //调用快速排序
        quickSort(arr, 0, arr.length - 1);


        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }


    }


    /**
     * 快排
     *
     * @param arr   要排序的数组
     * @param left  从left位置开始找
     * @param right 到right位置结束
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

//        定义移动的指针
        int i = left;
        int j = right;
//        定义基准数
        int base = arr[left];

        while (i < j) {
            // 从右向左找比base小的数据
            while (arr[j] >= base && i < j) {
                j--;
            }

            // 从左向右找比base大的数据
            while (arr[i] <= base && i < j) {
                i++;
            }
//            交换i和j位置的值
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

//        while循环结束 找到了基准数的位置 此时i和j相等
//        把base和当前i的位置的数据交换

        arr[left] = arr[i];
        arr[i] = base;

        //  i位置左边所有数据 重复上述步骤
        quickSort(arr, left, i - 1);
        // i位置右边所有数据 重复上述步骤
        quickSort(arr, i + 1, right);

    }
}
